package dp;

import java.util.Arrays;

/**
 * 分隔等和子集
 */
public class SeparateEqualSubset {

    public static void main(String[] args) {
        int[] set = new int[] {1,3,6,6};
        Arrays.sort(set);
        int sum = Arrays.stream(set)
                .reduce(Integer::sum)
                .orElse(0);
        if (sum % 2 != 0) {
            System.out.println(false);
        } else {
            boolean flag = knapsack(set,sum/2);
            System.out.println(flag);
        }
    }

    /**
     * 回溯法解法
     * @param startIndex 开始索引
     * @param set 原始数组
     * @param currSum 当前和
     * @param target 总和一半
     * @return
     */
    private static boolean backtrack(int startIndex, int[] set, int currSum,int target) {
        if (currSum == target) {
            return true;
        }
        if (currSum > target) {
            return false;
        }

        boolean flag = false;
        for (int i = startIndex; i < set.length; i++) {
            currSum+=set[i];
            flag = backtrack(i+1,set,currSum,target);
            currSum-=set[i];
        }
        return flag;
    }

    /**
     * 背包解法
     * @param arr 物品
     * @param sum 背包
     * @return
     */
    private static boolean knapsack(int[] arr,int sum) {
        // dp[j]表示 背包总容量（所能装的总重量）是j，放进物品后，背的最大重量为dp[j]。
        int[] dp = new int[sum+1];

        for (int i = 0; i < arr.length; i++) {
            for (int j = sum;j>=arr[i];j--) {
                dp[j] = Math.max(dp[j],dp[j-arr[i]] + arr[i]);
            }
        }
        Common.print1dArr(dp);
        return dp[sum] == sum;
    }
}
